In the context of indexes, a bitmap is a series of bits associated with a body of records and a particular criteria. Each record in the body of records has a corresponding bit in the bitmap. Each bit in the bitmap serves as a flag to indicate whether the record that corresponds to the bit satisfies the criteria associated with the bitmap. Typically, a bitmap index contains one bitmap for each unique value stored in a particular column of a table, and each bit of a bitmap indicates whether a corresponding row of the table contains a particular value in the particular column.
For example, FIG. 1A illustrates a table 100 that contains ten rows, where each row contains a name and a gender indicator. Rows 2, 3, 4, 5, 6, 8, 9 and 10 contain male gender indictors. Rows 1 and 7 contain female gender indicators. Therefore, the bitmap of table 100 for the criteria "GENDER=MALE" would be 0111110111, where the "1"s in positions 2-6 and 8-10 indicate that the second through sixth and eighth through tenth rows satisfy the "GENDER=MALE" criteria, and the zeros in the first and seventh positions indicate that first and seventh rows in table 100 do not satisfy the "GENDER=MALE" criteria.
When a new row is added to a table, a bit must be added to every bitmap associated with the table. For example, if an eleventh row is added to table 100, then an eleventh bit would be added to the end of the bitmap 0111110111 to indicate whether the new row satisfies the "GENDER=MALE" criteria.
Appending a bit to the end of a bitmap is a relatively trivial task. However, the overhead involved in managing bitmaps becomes significant when rows are added between existing rows, or when existing rows are deleted.
For example, assume that the second row is deleted from a table containing millions of rows. The bitmaps associated with the table will have to be rewritten without the bit associated with the deleted row. Similarly, if a row is inserted between the 2.sup.nd and 3.sup.rd rows of a table containing a million rows, all bitmaps associated with the table will have to be rewritten with an extra bit added between the pre-existing 2.sup.nd and 3.sup.rd bits.
Many database systems use row numbering schemes where new rows are inserted between existing rows on a regular basis. For example, FIG. 1B illustrates a table 102 where the numbers associated with each row are composed of two values. The first value indicates the block on which the row is stored and the second value indicates the slot number of the row within that block. FIG. 1C illustrates how the rows of table 102 are stored on disk.
A "GENDER=MALE" bitmap for table 102 would be identical to the bitmap described above for table 100. However, an eleventh row added to table 102 would not necessarily fall into the eleventh position in the row numbering scheme. For example, if the data for the eleventh record is stored in slot 2 of block 10, the new row will be assigned the numeric identifier "10.2", making the new row the second row of table 102. Similarly, if the data for the eleventh record is stored in slot 4 of block 12, the row will be assigned the numeric identifier "12.4" making the row the tenth row of table 102.
The overhead that would be required to insert and delete bits within large bitmaps in response to the insertion and deletion of rows can be significant. The larger the bitmaps, the greater the amount of overhead required to maintain the bitmaps. Therefore, the use of bitmaps is largely restricted to static bodies of data. For example, databases distributed on CDROMs may use bitmaps to provide fast searching capabilities. Under these conditions, the bitmaps require no maintenance because no changes are ever made to the data associated with the bitmaps.
Based on the foregoing, it is clearly desirable to provide a technique for efficiently using bitmaps to index bodies of data that may be updated. It is further desirable to provide a technique for using bitmaps to index bodies of data that use multi-level numeric identifiers to establish an order to the records contained in the bodies of data.